package 中等.贪心思想;

/**
 * 给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。
 * 每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。
 * 请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations
 */
public class 通过最少操作次数使数组的和相等_1775 {

    public static void main(String[] args) {

        System.out.println(minOperations(new int[]{6, 6}, new int[]{1}));

    }

    /**
     * 先求出 nums1 的和 sum1 ,和 nums2 的和 sum2
     * 他们的差值为 math.abs(sum2-sum1) = diff
     * 想要使得 diff == 0，的最小步骤，假设 sum1 < sum2
     * 在一步操作中，可以选择 nums1 的最小值 min 变成 6 ，diff 减少的值为 6-min
     * 或者 nums2 的最大值 max 变成 1，diff 减少的值为 max-1
     * 优先选择较大的方式
     * <p>
     * 可以使用计数排序降低排序的时间复杂度
     */
    public static int minOperations(int[] nums1, int[] nums2) {
        int count = 0;
        int sum1 = 0, sum2 = 0;
        int[] arr1 = new int[7];
        int[] arr2 = new int[7];
        for (int num : nums1) {
            arr1[num]++;
            sum1 += num;
        }
        for (int num : nums2) {
            arr2[num]++;
            sum2 += num;
        }
        if (sum1 > sum2) {
            int[] tempArr = arr1;
            arr1 = arr2;
            arr2 = tempArr;
        }

        int diff = Math.abs(sum2 - sum1);
        if (diff == 0) return 0;
        for (int i = 1; i <= 6; i++) {
            // 可优化，可一次性减去 i 的最大倍数
            while (arr1[i] > 0) {
                diff -= (6 - i);
                arr1[i]--;
                count++;
                if (diff <= 0) {
                    return count;
                }
            }

            while (arr2[7 - i] > 0) {
                diff -= (7 - i - 1);
                arr2[7 - i]--;
                count++;
                if (diff <= 0) {
                    return count;
                }
            }
        }
        return -1;
    }

}
